Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Microsoft Medium Problems
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Spiral Matrix

Problem Statement

Given a 2D matrix of size m x n, return the 1D array containing all elements of matrix in spiral order.

Examples

Example 1:

  • Input: matrix =
[[1,2,3,4],
 [5,6,7,8], 
 [9,10,11,12],
 [13,14,15,16]]
Image
  • Expected Output: [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
  • Justification: We have traversed the matrix in the spiral order.

Example 2:

  • Input: matrix =
[[10,20,30],
 [40,50,60],
 [70,80,90]]
  • Expected Output: [10,20,30,60,90,80,70,40,50]
  • Justification: The traversal starts at the top-left, moves right to the end of the row, then down the right column, then left along the bottom row, up the left column, and finally captures the center.

Example 3:

  • Input: matrix =
[[1,2],
 [3,4],
 [5,6]]
  • Expected Output: [1,2,4,6,5,3]
  • Justification: The traversal starts at the top-left, moves right, then down through the right column, and finally moves up the left column.

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

Solution

To solve this problem, we employ a systematic approach to traverse the matrix in layers, starting from the outermost layer and gradually moving towards the inner layers. We maintain four pointers to mark the boundaries of the current layer: top, bottom, left, and right. Initially, these pointers are set to the boundaries of the matrix. In each iteration, we traverse the current layer in a spiral order: from left to right, top to bottom, right to left, and bottom to top, adjusting the boundary pointers accordingly after each direction of traversal. This approach ensures that we visit each element exactly once, maintaining the spiral order.

This method is effective because it clearly defines the traversal order and boundaries, preventing overlaps or missed elements. By systematically shrinking the traversal area and moving inward, we ensure complete coverage of the matrix in a spiral pattern. This logical progression mirrors the spiral traversal requirement, making it a natural fit for solving the problem.

Step-by-step Algorithm

  • Initialize four pointers: top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1.
  • Create an empty list result to store the spiral order.
  • While (top <= bottom && left <= right):
    • Traverse from left to right at the top row. After traversing, increment top pointer.
    • Traverse from top to bottom at the right column. After traversing, decrement right pointer.
    • If (top <= bottom), traverse from right to left at the bottom row. After traversing, decrement bottom pointer.
    • If (left <= right), traverse from bottom to top at the left column. After traversing, increment left pointer.
  • Return the result list containing the elements in spiral order.

Algorithm Walkthrough

Image
  1. Initialize Boundary Pointers and Result Container:

    • Top = 0 (index of the first row)
    • Bottom = 3 (index of the last row)
    • Left = 0 (index of the first column)
    • Right = 3 (index of the last column)
    • Result = [] (an empty list to store the spiral order)
  2. First Outer Layer Traversal:

    • Traverse from Left to Right along the Top row:
      • Add elements 1, 2, 3, and 4 to Result.
    • Increment Top to 1 (moving the top boundary down to exclude the traversed row).
    • Traverse from Top to Bottom along the Right column:
      • Add elements 8, 12, and 16 to Result.
    • Decrement Right to 2 (moving the right boundary left to exclude the traversed column).
    • Since Top ≤ Bottom, traverse from Right to Left along the Bottom row:
      • Add elements 15, 14, and 13 to Result.
    • Decrement Bottom to 2 (moving the bottom boundary up to exclude the traversed row).
    • Since Left ≤ Right, traverse from Bottom to Top along the Left column:
      • Add elements 9 and 5 to Result.
    • Increment Left to 1 (moving the left boundary right to exclude the traversed column).
  3. Second Inner Layer Traversal:

    • Now, the pointers are adjusted to: Top = 1, Bottom = 2, Left = 1, Right = 2.
    • Traverse from Left to Right along the new Top row (which is the second row now):
      • Add elements 6 and 7 to Result.
    • Increment Top to 2.
    • Traverse from Top to Bottom along the Right column:
      • Add element 11 in the results.
    • Decrement Right to 1 (moving the right boundary left to exclude the traversed column).
    • Since Top ≤ Bottom, traverse from Right to Left along the Bottom row:
      • Add element 10 to Result.
    • Decrement Bottom to 1 (moving the bottom boundary up to exclude the traversed row).
    • Stop traversal as top > bottom, and left > right.
  4. Final Result Compilation:

    • After completing the spiral traversal correctly, the Result list now contains:
      [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
      
    • This sequence correctly represents the spiral order traversal of the given matrix.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • , where m * n is the total number of elements in the matrix. Each element is visited exactly once, making the time complexity linear in terms of the number of elements in the matrix.

Space Complexity

  • , disregarding the output array. The algorithm uses a constant amount of space for the pointers (top, bottom, left, right) and the result list's space is not considered part of the algorithm's space complexity as it is required for the output.
  • If we consider the output space, then the space complexity is , where m * n is the total number of elements in the matrix.
Spiral Matrix (medium)
Delete Node in a BST (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis